class Trie;
using TrieNode = Trie;

class Trie
{
public:
    // 插入一个字符串
    void insert(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (!node->children.count(c))
            {
                node->children[c] = new Trie;
            }
            node = node->children[c];
            ++node->viaCount;
        }
        ++node->endCount;
    }

    // 字符串s的数量
    int count(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (node->children.count(c))
            {
                node = node->children[c];
            }
            else
            {
                return 0;
            }
        }
        return node->endCount;
    }

    // 以s为前缀的字符串数量
    int prefixCount(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (node->children.count(c))
            {
                node = node->children[c];
            }
            else
            {
                return 0;
            }
        }
        return node->viaCount;
    }

    int nodeEndCount() const
    {
        return endCount;
    }

    int nodeViaCount() const
    {
        return viaCount;
    }

    bool existChild(char c) const
    {
        return children.count(c);
    }

    const TrieNode *child(char c) const
    {
        if (children.count(c))
        {
            return children.at(c);
        }
        return nullptr;
    }

    ~Trie()
    {
#ifdef TRIE_DECONSTRUCT
        for (auto &[_, child] : children)
        {
            if (child != nullptr)
            {
                delete child;
            }
            child = nullptr;
        }
#endif
    }

private:
    std::unordered_map<char, TrieNode *> children;
    int endCount = 0;
    int viaCount = 0;
};

class Solution
{
public:
    vector<string> removeSubfolders(vector<string> &folder)
    {
        sort(folder.begin(), folder.end(), [](auto &f1, auto &f2)
             { return f1.size() < f2.size(); });

        vector<string> result;
        Trie folderTrie;

        for (auto &f : folder)
        {
            int index = 0;
            const TrieNode *t = &folderTrie;
            bool isSub = false;
            while (index < f.size())
            {
                if (!t->existChild(f[index]))
                {
                    break;
                }
                t = t->child(f[index]);
                ++index;
                if (t->nodeEndCount() != 0)
                {
                    if (index < f.size() && f[index] == '/')
                    {
                        isSub = true;
                        break;
                    }
                    else if (index == f.size())
                    {
                        break;
                    }
                }
            }
            if (!isSub)
            {
                result.push_back(f);
                folderTrie.insert(f);
            }
        }

        return result;
    }
};